package cn.org.guhao.practice.go.model;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * 二叉树
 * @author guhao
 */
public class TreeNode implements Cloneable {

  private static final Logger logger = LoggerFactory.getLogger(TreeNode.class);

  private String data;

  private TreeNode left;

  private TreeNode right;

  @Override
  public TreeNode clone(){
    TreeNode cloneNode = null;
    try {
      cloneNode = (TreeNode)super.clone();
    } catch (CloneNotSupportedException e) {
      logger.error("clone error", e);
    }
    cloneNode.left = this.left.clone();
    cloneNode.right = this.right.clone();
    return cloneNode;
  }

  public TreeNode(String data) {
    this.data = data;
  }

  public String getData() {
    return data;
  }

  public void setData(String data) {
    this.data = data;
  }

  public TreeNode getLeft() {
    return left;
  }

  public void setLeft(TreeNode left) {
    this.left = left;
  }

  public TreeNode getRight() {
    return right;
  }

  public void setRight(TreeNode right) {
    this.right = right;
  }

  /**
   * 层次遍历
   * 实现思路：
   * 每个节点处理都从左向右压进链表中，在使用poll保证按照压进去的顺序再把取出节点的左右节点压进去
   * 压进去后死循环继续从链表中依次取出节点
   * @return
   */
  public String levelTraversal(){
    StringBuilder sortData = new StringBuilder();
    LinkedList<TreeNode> nodeLinkedList = new LinkedList<TreeNode>();
    nodeLinkedList.add(this);
    while (nodeLinkedList.size() != 0){
      TreeNode tn = nodeLinkedList.poll();
      sortData.append(tn.getData());
      if(tn.getLeft() != null){
        nodeLinkedList.add(tn.getLeft());
      }
      if(tn.getRight() != null){
        nodeLinkedList.add(tn.getRight());
      }
    }
    return sortData.toString();
  }

  /**
   * 前序遍历
   * @return
   */
  public List<String> preorderTraversal(){
    List<String> nodeList = new ArrayList<>();
    return preorderTraversal(this,nodeList);
  }

  /**
   * 前序遍历递归函数
   * @param node
   * @param nodeList
   * @return
   */
  private List<String> preorderTraversal(TreeNode node, List<String> nodeList){
    if(node == null){
      return nodeList;
    }
    nodeList.add(node.data);
    preorderTraversal(node.getLeft(),nodeList);
    preorderTraversal(node.getRight(),nodeList);
    return nodeList;
  }

  /**
   * 前序遍历（栈版本）
   * 实现思路：
   * @return
   */
  public List<String> preorderTraversalUseStack() {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode pNode = this;
    List<String> nodeList = new ArrayList<>();
    while (pNode != null || !stack.isEmpty()) {
      if (pNode != null) {
        // 把克隆的节点放到排序列表中
        nodeList.add(pNode.data);
        stack.push(pNode);
        pNode = pNode.left;
      } else {
        TreeNode node = stack.pop();
        pNode = node.right;
      }
    }
    return nodeList;
  }

}
